package DP.编辑距离;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 看草稿
 */
public class 编辑距离72_后序递归map版 {
    String s1;
    String s2;
    public int minDistance(String s1, String s2) {
        this.s1 = s1; this.s2 = s2;
        int minRes = back(s1.length()-1, s2.length()-1);
        return minRes;
    }
    /*
        // 1 无map
        private int back(int i, int j) {
            // 末 一方超 一定是 就剩删 [可能不只剩1个]j+1个 就等了 【因为右到左 先同 再动 的】
            if(i==-1){
                return j+1;
            }
            if(j==-1){
                return i+1;
            }

            // 特
            if(s1.charAt(i)==s2.charAt(j)){
                return back(i-1,j-1); // 跳过 不用操作 不加1
                // 少：递归终止用r，不用con
            }

            int zeng = back(i, j-1) + 1; // DP的后序 L+[cI]
            int shan = back(i-1 , j) + 1;
            int gai = back(i-1,j-1) + 1;

            return Math.min(gai, Math.min(zeng,shan));
        }
    */

    // 2 加map
    Map<String, Integer> ij_minLen_Map = new HashMap<>();
    private int back(int i, int j) {
        // 末 一方超 一定是 就剩删 [可能不只剩1个]j+1个 就等了 【因为右到左 先同 再动 的】
        if(i==-1){
            return j+1;
        }
        if(j==-1){
            return i+1;
        }

        // 特
        if(s1.charAt(i)==s2.charAt(j)){
            return back(i-1,j-1); // 跳过 不用操作 不加1
            // 少：递归终止用r，不用con
        }
        String key = i+","+j;
        if(ij_minLen_Map.containsKey(key)){
            return ij_minLen_Map.get(key);
        }

        int zeng = back(i, j-1) + 1; // DP的后序 L+[cI]
        int shan = back(i-1 , j) + 1;
        int gai = back(i-1,j-1) + 1;

        int curij_MinLen = Math.min(gai, Math.min(zeng,shan));
        ij_minLen_Map.put(key, curij_MinLen);
        return curij_MinLen;
    }



    @Test
    public void test() {
        System.out.println("RES:" + minDistance("rab", "apple"));
    }
}
